package pri.zjy.array;

import java.util.Arrays;

/**
 * @author zhangjy
 * @description 合并两个有序数组
 * <p>
 * 给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。
 * <p>
 * 请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。
 * <p>
 * 注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。
 * <p>
 * 进阶：你可以设计实现一个时间复杂度为 O(m + n) 的算法解决此问题吗？
 * @date 2025/3/25 15:09
 */
public class Merge_88 {

    public static void main(String[] args) {
        Merge_88 merge88 = new Merge_88();
//        int[] nums1 = {1, 2, 3, 0, 0, 0};
        int[] nums1 = {1};
//        int m = 3;
        int m = 1;
//        int[] nums2 = {2, 5, 6};
        int[] nums2 = new int[]{};
        int n = 0;
//        merge88.merge(nums1, m, nums2, n);
//        merge88.merge2(nums1, m, nums2, n);
//        merge88.merge3(nums1, m, nums2, n);
//        merge88.merge4(nums1, m, nums2, n);
        merge88.merge8(nums1, m, nums2, n);
        Arrays.stream(nums1).forEach(System.out::println);
    }

    public void merge8(int[] nums1, int m, int[] nums2, int n) {
        int[] nums3 = Arrays.copyOf(nums1, m);
        int i = 0, j = 0;
        while (i + j < m + n) {
            if (i < n && j < m) {
                // nums2、nums3都没处理完
                if (nums2[i] < nums3[j]) {
                    nums1[i + j] = nums2[i];
                    i++;
                } else {
                    nums1[i + j] = nums3[j];
                    j++;
                }
            } else if (i == n) {
                // nums2已经处理完
                nums1[i + j] = nums3[j];
                j++;
            } else if (j == m) {
                // nums3已经处理完
                nums1[i + j] = nums2[i];
                i++;
            }
        }
    }

    /**
     * 个解：倒序合并，先存入最大的数-双指针
     */
    public void merge6(int[] nums1, int m, int[] nums2, int n) {
        int i = m + n - 1, j = m - 1, k = n - 1;
        // 倒序放入nums1
        while (i >= 0) {
            if (j >= 0 && k >= 0) {
                // nums1、nums2原始数组还有数据可用（nums1、nums2都没处理完）
                if (nums1[j] > nums2[k]) {
                    nums1[i] = nums1[j];
                    j--;
                } else {
                    nums1[i] = nums2[k];
                    k--;
                }
            } else if (j < 0) {
                // nums1原始数组所有数据已存入新地方
                nums1[i] = nums2[k];
                k--;
            } else {
                // nums2原始数组所有数据已存入新地方
                nums1[i] = nums1[j];
                j--;
            }

            i--;
        }
    }

    /**
     * 官解3;双指针，不使用辅助数组
     * <p>
     * 分析：
     * <p>
     * 前面几种解法，为保证nums1的非递减，都使用辅助数组实现，是为了避免原nums1的前m个元素，尚未使用就被覆盖；
     * <p>
     * 而如果逆序操作，就不会出现覆盖前 m 个元素的问题。
     * <p>
     */
    public void merge5(int[] nums1, int m, int[] nums2, int n) {
        int i = m - 1, j = n - 1, index = m + n - 1, value;
        // 逆序存储，先把大的记录进去
        while (i >= 0 || j >= 0) {
            if (i < 0) {
                // nums3已经遍历完，直接处理nums2剩余元素
                value = nums2[j];
                j--;
            } else if (j < 0) {
                // nums2已经遍历完,直接处理nums3剩余元素
                value = nums1[i];
                i--;
            } else if (nums1[i] >= nums2[j]) {
                value = nums1[i];
                i--;
            } else {
                value = nums2[j];
                j--;
            }
            // 先记录再index--，不会越界
            nums1[index] = value;
            index--;
        }
    }

    /**
     * 官解2；
     * 辅助数组，while循环，最后一步才记录value
     */
    public void merge4(int[] nums1, int m, int[] nums2, int n) {
        int[] nums3 = Arrays.copyOf(nums1, m);
        int i = 0, j = 0, value;

        // 因为除i==m、j==n外，其余情况都属于i != m && j != n，所以可以优化去掉一层循环
        while (i < m || j < n) {
            if (i == m) {
                // nums3已经遍历完，直接处理nums2剩余元素
                value = nums2[j];
                j++;
            } else if (j == n) {
                // nums2已经遍历完,直接处理nums3剩余元素
                value = nums3[i];
                i++;
            } else if (nums3[i] <= nums2[j]) {
                // num3不大于nums2元素，就记录nums3
                value = nums3[i];
                i++;
            } else {
                // 记录nums2
                value = nums2[j];
                j++;
            }
            // 先加后记录，会越界；所以记录时要 减1
            nums1[i + j - 1] = value;
        }
    }

    /**
     * 官解1;
     * 直接合并，再快排；
     * 快排O(n) = O(logn)
     */
    public void merge3(int[] nums1, int m, int[] nums2, int n) {
        for (int i = m, j = 0; j < n; j++) {
            nums1[m] = nums2[j];
            m++;
        }
        Arrays.sort(nums1);
    }

    /**
     * 个解3（参考官解）；
     * 辅助数组，while循环。
     */
    public void merge2(int[] nums1, int m, int[] nums2, int n) {
        int[] nums3 = Arrays.copyOf(nums1, m);
        int i = 0, j = 0;

        while (i < m || j < n) {
            // num3不大于nums2元素，就记录到nums1
            if (i != m && j != n) {
                if (nums3[i] <= nums2[j]) {
                    nums1[i + j] = nums3[i];
                    i++;
                } else {
                    nums1[i + j] = nums2[j];
                    j++;
                }
            } else if (i == m) {
                // nums3已经遍历完，直接处理nums2剩余元素
                nums1[i + j] = nums2[j];
                j++;
            } else {
                // nums2已经遍历完,直接处理nums3剩余元素
                nums1[i + j] = nums3[i];
                i++;
            }
        }
    }

    /**
     * 个人双指针：利用辅助数组，直接比较，将满足条件的数存入nums1.
     * <p>
     * 分析：将不大于后者的值存入nums1，从而保证nums1满足 非递减顺序；使用nums3，是因为如果直接合并到数组 nums1 中，nums1中的元素可能会在取出之前被覆盖；
     * 其中，Arrays.copyOf() 对一维数组，以及一维数组元素类型是String、八大基本类型及其包装类（如char——>Character）来说是深拷贝，而一维数组的其它数据类型（如UserDTO）是浅拷贝；
     * <p>
     * 浅拷贝：是将对象的栈上的属性直接拷贝一份给新对象，对基本类型是没有问题，但引用类型会拷贝一个地址引用，本质使用的还是堆上的同一个对象，修改时会同时发生变化；如int[] B是浅拷贝int[] A的引用得到，修改B的元素，A也会改变。
     * <p>
     * 深拷贝：对于引用类似会新建一个引用对象，修改是独立、互不影响。
     * <p>
     * 时间复杂度：O(m+n)；其中，Arrays.copyOf()的时间复杂度为O(n)。
     * <p>
     * 指针移动单调递减，最多移动 m+n 次，因此时间复杂度为 O(m+n)。
     * <p>
     * 空间复杂度：O(m)。需要建立长度为 m
     * <p>
     */
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int[] nums3 = Arrays.copyOf(nums1, m);
        for (int i = 0, j = 0; i + j < m + n; ) {
            if (i < m && j < n) {
                // nums2、nums3都没处理完
                if (nums3[i] <= nums2[j]) {
                    nums1[i + j] = nums3[i];
                    i++;
                } else {
                    nums1[i + j] = nums2[j];
                    j++;
                }
            } else if (i == m) {
                // nums3已经处理完，只需要处理nums2
                nums1[i + j] = nums2[j];
                j++;
            } else if (j == n) {
                // nums2已经处理完，只需要处理nums3
                nums1[i + j] = nums3[i];
                i++;
            }
        }
    }

}
